In Polar code decoding, soft values, usually expressed as log-likelihood ratios, represent bits being decoded. Each bit of a codeword is decoded in turn using Successive Cancelation (“SC”) from beginning to end of a codeword in Polar decoding, namely a “Polar codeword”. If a single bit is incorrectly decoded, a conventional SC Polar code decoder may not revisit such bit to correct such an error. Along those lines, Successive Cancelation List (“SCL”) Polar code decoding may be used to address this limitation of SC Polar code decoding. SCL decoding looks at multiple possibilities, such as for example 2{circumflex over ( )}N possibilities, for N a bit length of a codeword to be decoded in order to reduce the likelihood of a decoding error. However, 2{circumflex over ( )}N possibilities for decoding may be too large for many applications.
In a conventional implementation, a list size is limited so as to reduce the amount of resources used to store and operate on an operating list for SCL decoding. As a result of having an operating list which is smaller than a corresponding search space, a choice is made during processing. Along those lines, possible codewords may be referred to as paths, because during decoding of codewords in-process bits thereof describe paths through a decision tree, where each decision is either a logic 1 or a logic 0. To facilitate each decision, each path is associated with a path metric which is a measure of a likelihood that such a path is correct based upon values of log-likelihood ratios (“LLRs”) output by a decoder.
During decoding, the number of paths may double in SCL decoding each time an information bit is encountered, as for each current path two output paths may be created. One of each such two created paths, namely a first created “child” or output path, has a logic 0 appended to a corresponding “parent” or input path, and another of each such two created paths, namely a second created “child” or output path, has a logic 1 appended to such a corresponding “parent” or input path. Each child path has a corresponding path metric determined for it. A list of path metrics corresponding to child paths is sorted, and such list may be culled to at most L child paths for having a corresponding L path metrics representing the “best” or most likely candidates, where L is a list size limit in such conventional implementation.